package solutions.leetcode.normal

import solutions.lib.TreeNode

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/binary-tree-coloring-game/">1145. 二叉树着色游戏</a>
 */
private class Solution1145 {
    fun btreeGameWinningMove(root: TreeNode?, n: Int, x: Int): Boolean {
        val node = findNode(root, x)
        val leftCount = count(node?.left)
        val rightCount = count(node?.right)
        return if ((leftCount + rightCount + 1) * 2 >= n) {
            rightCount * 2 >= n || leftCount * 2 >= n
        } else {
            true
        }
    }

    private fun count(node: TreeNode?): Int {
        if (node == null) return 0
        return 1 + count(node.left) + count(node.right)
    }

    private fun findNode(root: TreeNode?, x: Int): TreeNode? {
        if (root == null) {
            return null
        }
        if (root.`val` == x) {
            return root
        }
        findNode(root.left, x)?.apply { return this }
        return findNode(root.right, x)
    }
}

fun main() {
    println(Solution1145().btreeGameWinningMove(null, 0, 1))
}